class Task39Partition:
    def run(self, array):
        if len(array) is 0:
            return None

        middle = len(array) // 2
        start = 0
        end = len(array)
        index = self.partition(array, start, end)
        while index != middle:
            if index < middle:
                start = index + 1
            else:
                end = index
            index = self.partition(array, start, end)

        if self.check(array, array[index]):
            return array[index]
        else:
            return None

    def partition(self, array, start, end):
        k = start
        x = array[k]
        array[k], array[end - 1] = array[end - 1], array[k]
        i = start - 1
        for j in range(start, end):
            if array[j] < x:
                i += 1
                array[i], array[j] = array[j], array[i]
        i += 1
        array[i], array[end - 1] = array[end - 1], array[i]
        return i

    def check(self, array, n):
        count = 0
        for num in array:
            if num == n:
                count += 1
        return count > (len(array) // 2)


class Task39Count:
    def run(self, array):
        if len(array) == 0:
            return None

        count = 1
        result = array[0]
        for num in array[1:]:
            if count is 0:
                result = num
            if num == result:
                count += 1
            else:
                count -= 1

        if self.check(array, result):
            return result
        else:
            return None

    def check(self, array, n):
        count = 0
        for num in array:
            if num == n:
                count += 1
        return count > (len(array) // 2)
